home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1998 July / EnigmA AMIGA RUN 29 (1998)(G.R. Edizioni)(IT)[!][issue 1998-07 & 08].iso / earcd / phase5 / lha-ppc / src / slide.c < prev    next >
C/C++ Source or Header  |  1997-12-04  |  9KB  |  383 lines
  1. /***********************************************************
  2.     slide.c -- sliding dictionary with percolating update
  3. ***********************************************************/
  4. #include "slidehuf.h"
  5. #include "intrface.h"
  6.  
  7. #define PERCOLATE  1
  8. #define NIL        0
  9.  
  10. node *next = NULL;
  11. int unpackable;
  12. unsigned long origsize, compsize;
  13. unsigned short dicbit;
  14. unsigned short maxmatch;
  15. unsigned long count;
  16. unsigned short loc;
  17. unsigned char *text;
  18. int prev_char;
  19.  
  20. static unsigned long encoded_origsize;
  21.  
  22. static struct encode_option encode_define[2] = {
  23. #if defined(__STDC__) || defined(AIX)
  24. /* lh1 */
  25.     {(void(*)())output_dyn,
  26.      (void(*)())encode_start_fix,
  27.      (void(*)())encode_end_dyn},
  28. /* lh4, 5 */
  29.     {(void(*)())output_st1,
  30.     (void(*)())encode_start_st1,
  31.     (void(*)())encode_end_st1}
  32. #else
  33. /* lh1 */
  34.     {(int(*)())output_dyn,
  35.      (int(*)())encode_start_fix,
  36.      (int(*)())encode_end_dyn},
  37. /* lh4, 5 */
  38.     {(int(*)())output_st1,
  39.     (int(*)())encode_start_st1,
  40.     (int(*)())encode_end_st1}
  41. #endif
  42. };
  43.  
  44. static struct decode_option decode_define[7] = {
  45. /* lh1 */
  46.     {decode_c_dyn, decode_p_st0, decode_start_fix},
  47. /* lh2 */
  48.     {decode_c_dyn, decode_p_dyn, decode_start_dyn},
  49. /* lh3 */
  50.     {decode_c_st0, decode_p_st0, decode_start_st0},
  51. /* lh4 */
  52.     {decode_c_st1, decode_p_st1, decode_start_st1},
  53. /* lh5 */
  54.     {decode_c_st1, decode_p_st1, decode_start_st1},
  55. /* lzs */
  56.     {decode_c_lzs, decode_p_lzs, decode_start_lzs},
  57. /* lz5 */
  58.     {decode_c_lz5, decode_p_lz5, decode_start_lz5}
  59. };
  60.  
  61. static struct encode_option encode_set;
  62. static struct decode_option decode_set;
  63.  
  64. static node pos, matchpos, avail,
  65.         *position, *parent, *prev;
  66. static int remainder, matchlen;
  67. static unsigned char *level, *childcount;
  68. static unsigned short dicsiz;
  69. static unsigned short max_hash_val;
  70. static unsigned short hash1, hash2;
  71.  
  72. int encode_alloc(method)
  73. int method;
  74. {
  75.   if (method == 1) {
  76.     encode_set = encode_define[0];
  77.     maxmatch = 60;
  78.     dicbit = 12;
  79.   } else {
  80.     encode_set = encode_define[1];
  81.     maxmatch = MAXMATCH;
  82.     dicbit = 13;
  83.   }
  84.   while (1) {
  85.     dicsiz = 1 << dicbit;
  86.     max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
  87.     text = (unsigned char *)malloc(dicsiz * 2 + maxmatch);
  88.     level = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
  89.     childcount = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
  90. #if PERCOLATE
  91.     position = (node *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
  92. #else
  93.     position = (node *)malloc(dicsiz * sizeof(*position));
  94. #endif
  95.     parent     = (node *)malloc(dicsiz * 2 * sizeof(*parent));
  96.     prev       = (node *)malloc(dicsiz * 2 * sizeof(*prev));
  97.     next       = (node *)malloc((max_hash_val + 1) * sizeof(*next));
  98.     if (next == NULL || 
  99.     method > 1 && alloc_buf() == NULL) {
  100.       if (next) free(next);
  101.       if (prev) free(prev);
  102.       if (parent) free(parent);
  103.       if (position) free(position);
  104.       if (childcount) free(childcount);
  105.       if (level) free(level);
  106.       if (text) free(text);
  107.     } else {
  108.       break;
  109.     }
  110.     if (--dicbit < 12 )
  111.       /* error(MEMOVRERR, NULL); */
  112.       exit( 207 );
  113.   }
  114.   if (method == 5)
  115.     method = dicbit - 8;
  116.   return method;
  117. }
  118.  
  119. static void init_slide(void)
  120. {
  121.     node i;
  122.  
  123.     for (i = dicsiz; i <= dicsiz + UCHAR_MAX; i++) {
  124.         level[i] = 1;
  125. #if PERCOLATE
  126.             position[i] = NIL;  /* sentinel */
  127. #endif
  128.     }
  129.     for (i = dicsiz; i < dicsiz * 2; i++) parent[i] = NIL;
  130.     avail = 1;
  131.     for (i = 1; i < dicsiz - 1; i++) next[i] = i + 1;
  132.     next[dicsiz - 1] = NIL;
  133.     for (i = dicsiz * 2; i <= max_hash_val; i++) next[i] = NIL;
  134.     hash1 = dicbit - 9;
  135.     hash2 = dicsiz * 2;
  136. }
  137.  
  138. #define HASH(p, c) ((p) + ((c) << hash1) + hash2)
  139.  
  140. static /* inline */ node child(node q, unsigned char c)
  141.     /* q's child for character c (NIL if not found) */
  142. {
  143.     node r;
  144.  
  145.     r = next[HASH(q, c)];
  146.     parent[NIL] = q;  /* sentinel */
  147.     while (parent[r] != q) r = next[r];
  148.     return r;
  149. }
  150.  
  151. static /* inline */ void makechild(node q, unsigned char c, node r)
  152.     /* Let r be q's child for character c. */
  153. {
  154.     node h, t;
  155.  
  156.     h = HASH(q, c);
  157.     t = next[h];  next[h] = r;  next[r] = t;
  158.     prev[t] = r;  prev[r] = h;
  159.     parent[r] = q;  childcount[q]++;
  160. }
  161.  
  162. static /*inline*/ void split(node old)
  163. {
  164.     node new, t;
  165.  
  166.     new = avail;  avail = next[new];  childcount[new] = 0;
  167.     t = prev[old];  prev[new] = t;  next[t] = new;
  168.     t = next[old];  next[new] = t;  prev[t] = new;
  169.     parent[new] = parent[old];
  170.     level[new] = matchlen;
  171.     position[new] = pos;
  172.     makechild(new, text[matchpos + matchlen], old);
  173.     makechild(new, text[pos + matchlen], pos);
  174. }
  175.  
  176. static void insert_node(void)
  177. {
  178.     node q, r, j, t;
  179.     unsigned char c, *t1, *t2;
  180.  
  181.     if (matchlen >= 4) {
  182.         matchlen--;
  183.         r = (matchpos + 1) | dicsiz;
  184.         while ((q = parent[r]) == NIL) r = next[r];
  185.         while (level[q] >= matchlen) {
  186.             r = q;  q = parent[q];
  187.         }
  188. #if PERCOLATE
  189.             t = q;
  190.             while (position[t] < 0) {
  191.                 position[t] = pos;  t = parent[t];
  192.             }
  193.             if (t < dicsiz) position[t] = pos | SHRT_MIN;
  194. #else
  195.             t = q;
  196.             while (t < dicsiz) {
  197.                 position[t] = pos;  t = parent[t];
  198.             }
  199. #endif
  200.     } else {
  201.         q = text[pos] + dicsiz;  c = text[pos + 1];
  202.         if ((r = child(q, c)) == NIL) {
  203.             makechild(q, c, pos);  matchlen = 1;
  204.             return;
  205.         }
  206.         matchlen = 2;
  207.     }
  208.     for ( ; ; ) {
  209.         if (r >= dicsiz) {
  210.             j = maxmatch;  matchpos = r;
  211.         } else {
  212.             j = level[r];
  213.             matchpos = position[r] & SHRT_MAX;
  214.         }
  215.         if (matchpos >= pos) matchpos -= dicsiz;
  216.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  217.         while (matchlen < j) {
  218.             if (*t1 != *t2) {  split(r);  return;  }
  219.             matchlen++;  t1++;  t2++;
  220.         }
  221.         if (matchlen == maxmatch) break;
  222.         position[r] = pos;
  223.         q = r;
  224.         if ((r = child(q, *t1)) == NIL) {
  225.             makechild(q, *t1, pos);  return;
  226.         }
  227.         matchlen++;
  228.     }
  229.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  230.     t = next[r];  next[pos] = t;  prev[t] = pos;
  231.     parent[pos] = q;  parent[r] = NIL;
  232.     next[r] = pos;  /* special use of next[] */
  233. }
  234.  
  235. static void delete_node(void)
  236. {
  237. #if PERCOLATE
  238.         node q, r, s, t, u;
  239. #else
  240.         node r, s, t, u;
  241. #endif
  242.  
  243.     if (parent[pos] == NIL) return;
  244.     r = prev[pos];  s = next[pos];
  245.     next[r] = s;  prev[s] = r;
  246.     r = parent[pos];  parent[pos] = NIL;
  247.     if (r >= dicsiz || --childcount[r] > 1) return;
  248. #if PERCOLATE
  249.         t = position[r] & SHRT_MAX;
  250. #else
  251.         t = position[r];
  252. #endif
  253.     if (t >= pos) t -= dicsiz;
  254. #if PERCOLATE
  255.         s = t;  q = parent[r];
  256.         while ((u = position[q]) < 0) {
  257.             u &= SHRT_MAX;  if (u >= pos) u -= dicsiz;
  258.             if (u > s) s = u;
  259.             position[q] = (s | dicsiz);  q = parent[q];
  260.         }
  261.         if (q < dicsiz) {
  262.             if (u >= pos) u -= dicsiz;
  263.             if (u > s) s = u;
  264.             position[q] = (s | dicsiz) | SHRT_MIN;
  265.         }
  266. #endif
  267.     s = child(r, text[t + level[r]]);
  268.     t = prev[s];  u = next[s];
  269.     next[t] = u;  prev[u] = t;
  270.     t = prev[r];  next[t] = s;  prev[s] = t;
  271.     t = next[r];  prev[t] = s;  next[s] = t;
  272.     parent[s] = parent[r];  parent[r] = NIL;
  273.     next[r] = avail;  avail = r;
  274. }
  275.  
  276. /* static */void get_next_match(void)
  277. {
  278.     int n;
  279.  
  280.     remainder--;
  281.     if (++pos == dicsiz * 2) {
  282.         bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
  283.         n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
  284.         encoded_origsize += n;
  285.         remainder += n;  pos = dicsiz;
  286.     }
  287.     delete_node();  insert_node();
  288. }
  289.  
  290. void encode(interface)
  291. struct interfacing *interface;
  292. {
  293.     int lastmatchlen, dicsiz1;
  294.     node lastmatchpos;
  295.  
  296.     infile = interface -> infile;
  297.     outfile = interface -> outfile;
  298.     origsize = interface -> original;
  299.     compsize = count = 0L;
  300.     crc = unpackable = 0;
  301.     init_slide();  encode_set.encode_start();
  302.     dicsiz1 = dicsiz - 1;
  303.     pos = dicsiz + maxmatch;
  304.     memset(&text[pos], ' ', dicsiz);
  305.     remainder = fread_crc(&text[pos], dicsiz, infile);
  306.     encoded_origsize = remainder;
  307.     matchlen = 0;
  308.     insert_node();
  309.     while (remainder > 0 && ! unpackable) {
  310.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  311.         get_next_match();
  312.         if (matchlen > remainder) matchlen = remainder;
  313.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
  314.             encode_set.output(text[pos - 1], 0);
  315.             count++;
  316.         } else {
  317.             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  318.                    (pos - lastmatchpos - 2) & dicsiz1);
  319.             while (--lastmatchlen > 0) {
  320.                 get_next_match();
  321.                 count++;
  322.             }
  323.             if (matchlen > remainder) matchlen = remainder;
  324.         }
  325.     }
  326.     encode_set.encode_end();
  327.     interface -> packed = compsize;
  328.     interface -> original = encoded_origsize;
  329. }
  330.  
  331. void decode(interface)
  332. struct interfacing *interface;
  333. {
  334.     int i, j, k, c, dicsiz1, offset;
  335.  
  336.     infile = interface -> infile;
  337.     outfile = interface -> outfile;
  338.     dicbit = interface -> dicbit;
  339.     origsize = interface -> original;
  340.     compsize = interface -> packed;
  341.     decode_set = decode_define[interface -> method - 1];
  342.     crc = 0;
  343.     prev_char = -1;
  344.     dicsiz = 1 << dicbit;
  345.     text = (unsigned char *)malloc(dicsiz);
  346.     if (text == NULL)
  347.         /* error(MEMOVRERR, NULL); */
  348.         exit( errno );
  349.     memset(text, ' ', dicsiz);
  350.     decode_set.decode_start();
  351.     dicsiz1 = dicsiz - 1;
  352.     offset = (interface -> method == 6) ? 0x100 - 2 : 0x100 - 3;
  353.     count = 0;  loc = 0;
  354.     while (count < origsize) {
  355.         c = decode_set.decode_c();
  356.         if (c <= UCHAR_MAX) {
  357.             text[loc++] = c;
  358.             if (loc == dicsiz) {
  359.                 fwrite_crc(text, dicsiz, outfile);
  360.                 loc = 0;
  361.             }
  362.             count++;
  363.         } else {
  364.             j = c - offset;
  365.             i = (loc - decode_set.decode_p() - 1) & dicsiz1;
  366.             count += j;
  367.             for (k = 0; k < j; k++) {
  368.                 c = text[(i + k) & dicsiz1];
  369.                 text[loc++] = c;
  370.                 if (loc == dicsiz) {
  371.                     fwrite_crc(text, dicsiz, outfile);
  372.                     loc = 0;
  373.                 }
  374.             }
  375.         }
  376.     }
  377.     if (loc != 0) {
  378.         fwrite_crc(text, loc, outfile);
  379.     }
  380.     free(text);
  381. }
  382.  
  383.